package oct2013;

public class SearchinRotatedSortedArrayII {
	public boolean search(int[] A, int target) {
		int l = 0, r = A.length - 1, m;
		while (l <= r) {
			while (r > l && A[r] == A[l])
				r--;
			m = l + r >> 1;
			if (A[m] == target)
				return true;
			if (A[m] >= A[l]) {
				if (target >= A[m] || target < A[l]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			} else {
				if (target < A[l] && target >= A[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
		}
		return false;
	}
}
